package pro.softzhang.algo.lc100;

import pro.softzhang.algo.flag.difficulty.DYellow;
import pro.softzhang.algo.flag.knowledge.KDynamicPlanning;
import pro.softzhang.algo.flag.theme.TRobber;
import pro.softzhang.algo.flag.x.XClassic;
import pro.softzhang.algo.flag.x.XOptimal;

import java.util.Arrays;

/**
 * https://leetcode.cn/problems/house-robber/solution/dong-tai-gui-hua-jie-ti-si-bu-zou-xiang-jie-cjavap/
 */
@DYellow
@TRobber
@XClassic
public class LC198_HouseRobber {
    public static void main(String[] args) {
        int[] houses = new int[]{1,2,3,1};
        int max = new Solution().rob(houses);
        System.out.println(max);
    }

    @XOptimal
    @KDynamicPlanning
    static
    class Solution {
        public int rob(int[] nums) {
            int[] dp = new int[2];
            dp[0] = nums[0];
            if(nums.length > 1) {
                dp[1] = Math.max(nums[0], nums[1]);
            }

            for (int i = 2; i < nums.length; i++) {
                dp[i % 2] = Math.max(dp[(i - 2) % 2] + nums[i], dp[(i - 1) % 2]);
            }

            return dp[(nums.length - 1) % 2];
        }
    }

    /**
     * 递推解法
     */
    static
    class Solution1 {
        public int rob(int[] nums) {
            int[] dp = new int[nums.length + 1];
            dp[0] = 0;
            dp[1] = nums[0];
            for (int i = 2; i <= nums.length; i++) {
                dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
            }
            return dp[nums.length];
        }
    }

    /**
     * 回溯解法
     */
    static
    class Solution2 {
        public int rob(int[] nums) {
            int n = nums.length;
            int[] cache = new int[n];
            Arrays.fill(cache, -1);
            return dfs(n - 1, nums, cache);
        }

        private int dfs(int i, int[] nums, int[] cache) {
            if (i < 0) {
                return 0;
            }

            if (cache[i] != -1) {
                return cache[i];
            }

            int max = Math.max(dfs(i - 1, nums, cache), dfs(i - 2, nums, cache) + nums[i]);
            cache[i] = max;
            return max;
        }
    }

    static
    class Solution3 {
        public int rob(int[] nums) {
            int n = nums.length;
            return dfs(0, nums);
        }

        private int dfs(int i, int[] nums) {
            if (i >= nums.length) {
                return 0;
            }

            return Math.max(dfs(i + 1, nums), dfs(i  + 2, nums) + nums[i]);
        }
    }
}
